When implementing encryption software, if the key, encryption algorithm and the like are implemented without any countermeasures, the software can be analyzed and easily used maliciously. For this reason, there are demands for tamper-resistant software that is difficult to analyze. As one tamper-resistant software technique, Patent Document 1 discloses a scheme for transforming operations and operation domains to make the original operation domain difficult to guess. This scheme makes the software difficult to analyze.
The transformation used in the described scheme is linear transformation or the like. For instance, in order to transform an addition of a key and data, the key and data are transformed, the obtained data is added in a transformed domain, and the result of the addition is inverse-transformed. This obtains the same result as adding the key and the data. When applied to an encryption program, a decryption program, or the like that uses shared key encryption, this kind of obfuscated addition method increases the security of the program against attacks that analyze programs to obtain keys.
The following describes a specific example of the technique disclosed by Patent Document 1.
Here, a description is given of an addition program that outputs an operation result a+b with respect to input a and b, and is composed of a transformation module, a main operation module, an inverse transformation module, and an output module.
The transformation module holds integers k1 and k2. The inverse transformation module receives input values a and b, and with use of the held integers k1 and k2, transforms the input values a and b into ta=k1×a+k2 and tb=k1×b+k2, respectively. Note that “×” represents multiplication. Next, the main operation module calculates tab=ta+tb with respect to the values ta and tb. The inverse transformation module calculates c=(tab−2×k2)/k1 with respect to tab. The output module outputs an operation result c.
According to the above-described processing, from tab=ta+tb=k1×a+k2+k1×b+k2=k1×(a+b)+2×k2, (tab−2×k2)/k1=a+b is established. Consequently, c=a+b, and the addition program can calculate the addition result of a and b from the input values a and b.
Here, if the transformation module and the inverse transformation module are realized in a manner that makes analysis difficult, the only data that a third party (analyzer) will be able to obtain by analyzing is the values ta, tb and tab. Since a and b are difficult to guess from these values, a and b can be concealed.
In Patent Document 1, the data is transformed according to linear transformation, thus making the data itself difficult to analyze. However, the type of operation, in other words addition, is the same in the transformation destination, and therefore this system does not go as far as to conceal the type of operation.
In patent document 2, the type of operation is concealed by transforming addition into multiplication or addition of a group of an elliptic curve based on a discrete logarithm problem that has a trapdoor and therefore can be easily solved by a party in possession of certain information (i.e., the trapdoor).
A description is now given of a conventional elliptic DSA (digital signature algorithm) signature scheme. Note that the following description will be kept brief since details of a conventional elliptic DSA signature can be found on page 4 of Non-Patent Document 3.
(1) Parameters
In a conventional elliptic DES signature scheme, the parameters are variables a and b in an equation y^2=x^3+a×x+b of an elliptic curve, a finite field GF(p) of the elliptic curve E, a base point P and an order q of the base point. Here, x^y denotes the y-th power of x, and q and P satisfy q*P=O. O is a zero element of an elliptic curve group, “*” denotes a scalar multiplication on an elliptic curve, and q*P expresses a point on an elliptic curve obtained by adding q base points Ps.
(2) Private Key and Public Key
Let the private key be ks (0<ks<q), and let the public key be KP=ks*P.
(3) Signature Generating
In signature generating in a conventional elliptic DSA signature scheme, a digital signature S of a message m that is to be signed is generated according to the following steps.
Step S1: Calculate h=Hash(m), where Hash(m) is a hash value of m. The hash function used to obtain the hash value may, for instance, be SHA-1. Details of hash functions can be found in Non-Patent Document 1, pages 192-195.
Step S2: Select a random number k, and calculate a point R=k*P on an elliptic curve.
Step S3: Calculate r=x(R)mod q, where x(R) denotes the x coordinate of R.
Step S4: Calculate s=(h+r×ks)/k mod q.
Step S5: Output S=(r,s), end.
(4.) Signature Verification
In signature verification in a conventional elliptic DSA signature scheme, the digital signature S is subjected to verification and a verification result (successful or failure) is output according to the following steps.
Step S10: Calculate h=Hash(m).
Step S11: Calculate R′=(h/s mod q)*P+(r/s mod q)*KP, let r′=x(R′).
Step S12: Check whether r=r′. If true, output “success”. If false, output “failure” and end processing.    Patent Document 1: U.S. Pat. No. 6,594,761    Patent Document 2: International Publication No. 2005/098795 pamphlet    Patent Document 3:U.S. Pat. No. 3,402,441 specification    Non-Patent Document 1: Tatsuaki OKAMOTO and Hirosuke YAMAMOTO “Gendai Angou” (“Modern Encryption”), Sangyou Tosho, 1997    Non-Patent Document 2: Henri Cohen “A Course in Computational Algebraic Number Theory”, GTM 138, Springer-Verlag, 1993, pp. 16-19    Non-Patent Document 3: I. Blake, G. Seroussi and N. Smart, “Elliptic Curves in Cryptography”, CAMBRIDGE UNIVERSITY PRESS, 1999    Non-Patent Document 4: N. Kunihiro and K. Koyama, “Two Discrete Log Algorithms for Super-Anomalous Elliptic Curves”, SCIS '99, 1999, pp. 869-874